package cn.mayday.algorithms.year2021.month1.优先搜索二叉搜索;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * <p>
 * 例如，给出
 * <p>
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * <p>
 * 返回如下的二叉树：
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * <p>
 * <p>
 * <p>
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 5000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Mayday05
 * @date 2021/1/3 14:55
 */
public class Off07BuildTree {

    public static void main(String[] args) {

    }

    HashMap<Integer, Integer> middleIndexMap = new HashMap<>();//标记中序遍历
    int[] preorder;//保留的先序遍历，方便递归时依据索引查看先序遍历的值

    // 方法一：基本是递归，涉及到二叉树的题目都是递归
    // 递归三元素
    // (1) 递推参数，根节点在前序遍历的索引root,子树在中序遍历的左边界left、子树在中序遍历的右边界right；
    // (2) 终止条件：当left > right,代表已经越过叶节点，此时返回null
    // (3) 递推工作： 1、建立根节点node, 节点值为preorder[root] 2、 划分左右子树，查找根节点在中序遍历inorder中的索引i
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }

        this.preorder = preorder;

        int length = inorder.length;
        //将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
        for (int i = 0; i < length; i++) {
            middleIndexMap.put(inorder[i], i);
        }
        TreeNode root = recursive(0, 0, length - 1);

        return root;
    }

    public TreeNode recursive(int preorderRoot, int inorderLeft, int inorderRight) {
        if (inorderLeft > inorderRight) {
            return null;
        }
        //获取root节点
        int rootVal = preorder[preorderRoot];
        TreeNode root = new TreeNode(rootVal);

        int idx = middleIndexMap.get(rootVal); //获取在中序遍历中根节点所在索引，以方便获取左子树的数量

        //左子树的根的索引为先序中的根节点+1
        //递归左子树的左边界为原来的中序inorderLeft
        //递归右子树的右边界为中序中的根节点索引-1
        root.left = recursive(preorderRoot + 1, inorderLeft, idx - 1);

        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的有边界为中序中原来右子树的边界inorderRight
        root.right = recursive(preorderRoot + (idx - inorderLeft) + 1, idx + 1, inorderRight);

        return root;
    }


/**
 * 知识点：
 *
 *     前序遍历列表：第一个元素永远是 【根节点 (root)】
 *     中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】
 *
 * 算法思路：
 *
 *     通过【前序遍历列表】确定【根节点 (root)】
 *     将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】
 *     递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】
 */

    /**
     * 二叉树定义
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
